package fun.parser.postfix;

/**
 * ��׺���ʽת��Ϊ��׺���ʽ�Ĳ��裺
 * 1����ʼ��һ���ն�ջ��������ַ�����ÿա� 
 * 2�������Ҷ�����׺���ʽ��ÿ��һ���ַ� 
 * 3������ַ��ǲ���������ӵ�����ַ� 
 * 4������ַ��Ǹ�����������pop��������ֱ���������ţ�opening parenthesis�������ȼ��ϵ͵Ĳ�����
 *   ����ͬһ���ȼ����ҽ�Ϸ�š������������ѹ�루push����ջ�� 
 * 5������ַ��Ǹ������ţ�����ѹ���ջ�� 
 * 6������ַ��Ǹ������ţ�closing parenthesis��������������ǰ���������в�����Ȼ���������ӵ����
 *   �ַ� 
 * 7�����������ַ��ĩβ���������в�������ӵ�����ַ� 
 */
import java.io.IOException;
import java.io.Reader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

import fun.parser.LexerException;
import fun.parser.lexer.Lexer;
import fun.parser.lexer.Token;
import fun.parser.lexer.TokenType;
import fun.parser.util.TokenUtils;

public class PostfixParser {
    private Lexer lexer = null;
    // lastToken���ж� "+","-" ��һԪ/��Ԫ������������
    protected Token lastToken = null;

    public PostfixParser() {
	// lexer will be lazy initialized
	this(null);
    }

    protected PostfixParser(Lexer lexer) {
	this.lexer = lexer;
	this.lastToken = null;
    }

    public void setSource(Reader source) {
	if (null == lexer)
	    lexer = new Lexer();
	lexer.setSource(source);
    }

    public PostfixProgram parse() throws IOException, LexerException {
	return this.parse(TokenType.END);
    }

    /**
     * ��׺���ʽת��׺���ʽ
     * 
     * @param ends
     *            ���ʽ����ı��
     * @return postfix expression
     * @throws LexerException
     * @throws IOException
     */
    protected PostfixProgram parse(TokenType... ends) throws IOException, LexerException, NullPointerException {
	// e.g.: 2 * sin( 1 + sin( 1+ 2^3 ) ) / 3
	Token lookahead = null;
	Stack<PostfixNode> postfix = new Stack<PostfixNode>();
	Stack<PostfixNode> operators = new Stack<PostfixNode>();
	while (true) {
	    lookahead = lexer.nextToken();
	    // =========================================
	    // reach the end
	    if (true == this.isEnd(ends, lookahead)) {
		while (false == operators.empty())
		    postfix.push(operators.pop());
		Collections.reverse(postfix);
		return new PostfixProgram(postfix);
	    }// end of end
	    // ==============================================
	    // handle operator
	    if (true == TokenUtils.isOperator(lookahead)) {
		// operator
		TokenType type = lookahead.getTokenType();
		switch (type) {
		case LEFT_P:
		    operators.push(PostfixNode.newOperator(lookahead));
		    break;
		case RIGHT_P:
		    // �����ſ����Ǹı���ʽ���ȼ��ģ�Ҳ������"����"�Ľ����־
		    if (false == this.contains(operators, TokenType.LEFT_P)) {
			// ȷ��������������Ǻ������ı�־
			lexer.pushback(lookahead);
			while (false == operators.empty())
			    postfix.push(operators.pop());
			Collections.reverse(postfix);
			return new PostfixProgram(postfix);
		    }
		    while (false == operators.empty()) {
			PostfixNode inOp = operators.peek();
			if (inOp.getTokenType() == TokenType.LEFT_P) {
			    operators.pop();
			    break;
			}
			postfix.push(operators.pop());
		    }
		    break;
		default:
		    PostfixNode outOp = PostfixNode.newOperator(lookahead);
		    while (false == operators.empty()) {
			PostfixNode inOp = operators.peek();
			if (inOp.getTokenType() == TokenType.LEFT_P || inOp.getPriority() < outOp.getPriority())
			    break;
			postfix.push(operators.pop());
		    }
		    operators.push(outOp);
		}
	    } // end of operator
	    // =====================================================
	    // handle operand
	    else {
		// handle numerical value
		if (true == TokenUtils.isNumeric(lookahead))
		    postfix.push(PostfixNode.newOperand(lookahead));
		// ����������������ˣ�����lookaheadֻ������ IDENTIFIER ��
		if (TokenType.IDENTIFIER == lookahead.getTokenType()) {
		    // ��Ҫ��ǰ�࿴һ��token��ȷ�ϵ����Ǳ������Ǻ���
		    Token next = this.lexer.nextToken();
		    // ȷ��Ϊ����
		    if (TokenType.LEFT_P == next.getTokenType()) {
			next = lexer.nextToken();
			List<PostfixProgram> args = new ArrayList<PostfixProgram>();
			while (TokenType.RIGHT_P != next.getTokenType()) {
			    // parse arguments list
			    lexer.pushback(next);
			    PostfixParser argParser = new PostfixParser(lexer);
			    args.add(argParser.parse(TokenType.COMMA));
			    next = lexer.nextToken();
			}// end of parsing args
			// now 'next' should be RIGHT_P
			postfix.push(PostfixNode.newFunction(lookahead, args.toArray(new PostfixProgram[0])));
		    }// end of Function
		    // ȷ��Ϊ����,��Ҫ pushback( next )
		    else {
			this.lexer.pushback(next);
			postfix.push(PostfixNode.newOperand(lookahead));
		    }// end of Variable
		}// end of IDENTIFIER
	    }// end of operand
	    this.lastToken = lookahead;
	}// end of while
    }

    private boolean isEnd(TokenType[] ends, Token token) {
	if (null == ends)
	    throw new NullPointerException("");
	TokenType type = token.getTokenType();
	for (int i = 0; i < ends.length; i++)
	    if (type == ends[i])
		return true;
	return false;
    }

    private boolean contains(Stack<PostfixNode> stack, TokenType type) {
	for (int i = 0; i < stack.size(); i++)
	    if (type == stack.get(i).getTokenType())
		return true;
	return false;
    }
}
